import java.util.Stack;

/**
* @description: 962. 最大宽度坡
* @author hewei
* @date 2022/9/26 14:56
* @version 1.0
*/

public class MaxWidthRamp {

    public int maxWidthRamp1(int[] nums) {
        int n = nums.length;
        int[] maxNums = new int[n];
        int max = nums[n - 1];
        for (int i = n - 1; i >= 0; i--) {
           max = Math.max(max, nums[i]);
           maxNums[i] = max;
        }
        int l = 0;
        int r = 0;
        int ans = 0;
        while (r < n - 1) {
            if (maxNums[r + 1] >= nums[l]) {
                ++r;
                ans = r - l;
            } else {
                ++l;
                ++r;
            }
        }
        return ans;
    }

    public int maxWidthRamp(int[] nums) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] <= nums[stack.peek()]) stack.push(i);
        }
        int ans = 0;
        for (int i = nums.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && nums[i] >= nums[stack.peek()]) {
                Integer pop = stack.pop();
                ans = Math.max(ans, i - pop);
            }
        }
        return ans;
    }
}
